package cn.kuick.match2.test7;

import java.util.ArrayList;
import java.util.Stack;

public class ConvertA2B {

	public static boolean isMatch(StringBuffer source, StringBuffer target, Stack<Integer> sb) {
		if (source.equals(target)) {
			return true;
		}
		
		return false;
	}
	
	public static boolean isOk(ArrayList<Integer[]> output, Stack<Integer> sb) {
		int min = findMin(output);
		
		if (sb.size() <= min) {
			return true;
		}
		
		return false;
	}
	
	public static StringBuffer handle(StringBuffer source, StringBuffer target, int i, int j) {
		switch(j) {
		case 0:
			if (i < source.length() && i < target.length()) {
				source.setCharAt(i, target.charAt(i));
			}
			break;
		case 1:
			if (i < source.length()) {
				source.replace(i, i+1, "");
			}
			break;
		case 2:
			if (i < source.length() && i < target.length()) {
				source.insert(i, target.charAt(i));
			}
			break;
		}
		
		return source;
	}
	
	public static void innerOutput(int i, StringBuffer source, StringBuffer target, ArrayList<Integer[]> output, Stack<Integer> sb) {
		for(int j=0; j<3; j++) {
			sb.add(j);
			
			String old = source.toString();
			handle(source, target, i, j);
			
			if (isMatch(source, target, sb)) {
				output.add(sb.toArray(new Integer[sb.size()]));
			} else {
				if (isOk(output, sb) && i < target.length()) {
					innerOutput(i + 1, source, target, output, sb);
				}
			}
			
			sb.pop();
			source = new StringBuffer(old);
		}
	}
	
	public static int findMin(ArrayList<Integer[]> output) {
		int min = Integer.MAX_VALUE;
		
		for(int i=0; i<output.size(); i++) {
			min = Math.min(min, output.get(i).length);
		}
		
		return min;
	}
	
	public static int handle(String a, String b) {
		ArrayList<Integer[]> output = new ArrayList<>();
		
		Stack<Integer> sb = new Stack<>();
		StringBuffer a1 = new StringBuffer(a);
		StringBuffer b1 = new StringBuffer(b);
		
		innerOutput(0, a1, b1, output, sb);
		
		int len = findMin(output);
		
		return len;
	}
	
	public static void main(String[] args) {
		int output = handle("kitten", "sitting");
		System.out.println(output);
	}
}
